{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Candies You Can Get from Boxes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #graph #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #图 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxCandies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #你能从盒子里获得的最大糖果数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你&nbsp;<code>n</code>&nbsp;个盒子，每个盒子的格式为&nbsp;<code>[status, candies, keys, containedBoxes]</code>&nbsp;，其中：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>状态字&nbsp;<code>status[i]</code>：整数，如果&nbsp;<code>box[i]</code>&nbsp;是开的，那么是 <strong>1&nbsp;</strong>，否则是 <strong>0&nbsp;</strong>。</li>\n",
    "\t<li>糖果数&nbsp;<code>candies[i]</code>: 整数，表示&nbsp;<code>box[i]</code> 中糖果的数目。</li>\n",
    "\t<li>钥匙&nbsp;<code>keys[i]</code>：数组，表示你打开&nbsp;<code>box[i]</code>&nbsp;后，可以得到一些盒子的钥匙，每个元素分别为该钥匙对应盒子的下标。</li>\n",
    "\t<li>内含的盒子&nbsp;<code>containedBoxes[i]</code>：整数，表示放在&nbsp;<code>box[i]</code>&nbsp;里的盒子所对应的下标。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个&nbsp;<code>initialBoxes</code> 数组，表示你现在得到的盒子，你可以获得里面的糖果，也可以用盒子里的钥匙打开新的盒子，还可以继续探索从这个盒子里找到的其他盒子。</p>\n",
    "\n",
    "<p>请你按照上述规则，返回可以获得糖果的 <strong>最大数目&nbsp;</strong>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>status = [1,0,1,0], candies = [7,5,4,100], keys = [[],[],[1],[]], containedBoxes = [[1,2],[3],[],[]], initialBoxes = [0]\n",
    "<strong>输出：</strong>16\n",
    "<strong>解释：\n",
    "</strong>一开始你有盒子 0 。你将获得它里面的 7 个糖果和盒子 1 和 2。\n",
    "盒子 1 目前状态是关闭的，而且你还没有对应它的钥匙。所以你将会打开盒子 2 ，并得到里面的 4 个糖果和盒子 1 的钥匙。\n",
    "在盒子 1 中，你会获得 5 个糖果和盒子 3 ，但是你没法获得盒子 3 的钥匙所以盒子 3 会保持关闭状态。\n",
    "你总共可以获得的糖果数目 = 7 + 4 + 5 = 16 个。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>status = [1,0,0,0,0,0], candies = [1,1,1,1,1,1], keys = [[1,2,3,4,5],[],[],[],[],[]], containedBoxes = [[1,2,3,4,5],[],[],[],[],[]], initialBoxes = [0]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：\n",
    "</strong>你一开始拥有盒子 0 。打开它你可以找到盒子 1,2,3,4,5 和它们对应的钥匙。\n",
    "打开这些盒子，你将获得所有盒子的糖果，所以总糖果数为 6 个。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>status = [1,1,1], candies = [100,1,100], keys = [[],[0,2],[]], containedBoxes = [[],[],[]], initialBoxes = [1]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>status = [1], candies = [100], keys = [[]], containedBoxes = [[]], initialBoxes = []\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>status = [1,1,1], candies = [2,3,2], keys = [[],[],[]], containedBoxes = [[],[],[]], initialBoxes = [2,1,0]\n",
    "<strong>输出：</strong>7\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= status.length &lt;= 1000</code></li>\n",
    "\t<li><code>status.length == candies.length == keys.length == containedBoxes.length == n</code></li>\n",
    "\t<li><code>status[i]</code> 要么是&nbsp;<code>0</code>&nbsp;要么是&nbsp;<code>1</code> 。</li>\n",
    "\t<li><code>1 &lt;= candies[i] &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= keys[i].length &lt;= status.length</code></li>\n",
    "\t<li><code>0 &lt;= keys[i][j] &lt; status.length</code></li>\n",
    "\t<li><code>keys[i]</code>&nbsp;中的值都是互不相同的。</li>\n",
    "\t<li><code>0 &lt;= containedBoxes[i].length &lt;= status.length</code></li>\n",
    "\t<li><code>0 &lt;= containedBoxes[i][j] &lt; status.length</code></li>\n",
    "\t<li><code>containedBoxes[i]</code>&nbsp;中的值都是互不相同的。</li>\n",
    "\t<li>每个盒子最多被一个盒子包含。</li>\n",
    "\t<li><code>0 &lt;= initialBoxes.length&nbsp;&lt;= status.length</code></li>\n",
    "\t<li><code>0 &lt;= initialBoxes[i] &lt; status.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-candies-you-can-get-from-boxes](https://leetcode.cn/problems/maximum-candies-you-can-get-from-boxes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-candies-you-can-get-from-boxes](https://leetcode.cn/problems/maximum-candies-you-can-get-from-boxes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,0,1,0]\\n[7,5,4,100]\\n[[],[],[1],[]]\\n[[1,2],[3],[],[]]\\n[0]', '[1,0,0,0,0,0]\\n[1,1,1,1,1,1]\\n[[1,2,3,4,5],[],[],[],[],[]]\\n[[1,2,3,4,5],[],[],[],[],[]]\\n[0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        n = len(status)\n",
    "        res = 0\n",
    "        count = 0\n",
    "        while len(initialBoxes) != 0:\n",
    "            count += 1\n",
    "            s = initialBoxes.pop(0)\n",
    "            if status[s] == 1:\n",
    "                res += candies[s]\n",
    "                count = 0  # 需要重新遍历一遍，防止遗漏，重置count\n",
    "                for i in containedBoxes[s]:\n",
    "                    initialBoxes.append(i)\n",
    "                for i in keys[s]:\n",
    "                    status[i] = 1\n",
    "            else:\n",
    "                initialBoxes.append(s)\n",
    "            if count == n:  # 开完已开的之后，用已有的钥匙，全都遍历了一遍\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        q = []\n",
    "        ans = 0\n",
    "        k = set()\n",
    "        locks = set()\n",
    "        for b in initialBoxes:\n",
    "            if status[b]: q.append(b)\n",
    "            else: locks.add(b)\n",
    "        while q:\n",
    "            box = q.pop(0)\n",
    "            ans += candies[box]\n",
    "            for b in containedBoxes[box]:\n",
    "                if status[b] == 1 or b in k:\n",
    "                    q.append(b)\n",
    "                else:\n",
    "                    locks.add(b)\n",
    "            for key in keys[box]:\n",
    "                k.add(key)\n",
    "                if key in locks:\n",
    "                    locks.remove(key)\n",
    "                    q.append(key)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        ans, n = 0, len(status)\n",
    "        visited = [False] * n\n",
    "        has_box = [False] * n\n",
    "        can_open = [i == 1 for i in status]\n",
    "        q = collections.deque()\n",
    "        for box in initialBoxes:\n",
    "            has_box[box] = True\n",
    "            if can_open[box]:\n",
    "                ans += candies[box]\n",
    "                q.append(box)\n",
    "                visited[box] = True\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            for box in containedBoxes[cur]:\n",
    "                has_box[box] = True\n",
    "                if not visited[box] and can_open[box]:\n",
    "                    ans += candies[box]\n",
    "                    q.append(box)\n",
    "                    visited[box] = True\n",
    "            for key in keys[cur]:\n",
    "                can_open[key] = True\n",
    "                if not visited[key] and has_box[key]:\n",
    "                    ans += candies[key]\n",
    "                    q.append(key)\n",
    "                    visited[key] = True\n",
    "        return ans\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        n = len(status)\n",
    "        can_open = [status[i] == 1 for i in range(n)]\n",
    "        has_box, used = [False] * n, [False] * n\n",
    "        \n",
    "        q = collections.deque()\n",
    "        ans = 0\n",
    "        for box in initialBoxes:\n",
    "            has_box[box] = True\n",
    "            if can_open[box]:\n",
    "                q.append(box)\n",
    "                used[box] = True\n",
    "                ans += candies[box]\n",
    "        \n",
    "        while len(q) > 0:\n",
    "            big_box = q.popleft()\n",
    "            for key in keys[big_box]:\n",
    "                can_open[key] = True\n",
    "                if not used[key] and has_box[key]:\n",
    "                    q.append(key)\n",
    "                    used[key] = True\n",
    "                    ans += candies[key]\n",
    "            for box in containedBoxes[big_box]:\n",
    "                has_box[box] = True\n",
    "                if not used[box] and can_open[box]:\n",
    "                    q.append(box)\n",
    "                    used[box] = True\n",
    "                    ans += candies[box]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        ans = 0\n",
    "        my_keys = set()\n",
    "        my_boxes = set(initialBoxes)\n",
    "        while my_boxes:\n",
    "            _my_boxes = copy.copy(my_boxes)\n",
    "            new_boxes = set()\n",
    "            for box in my_boxes:\n",
    "                if status[box] or box in my_keys:\n",
    "                    ans += candies[box]\n",
    "                    for k in keys[box]:\n",
    "                        my_keys.add(k)\n",
    "                    for b in containedBoxes[box]:\n",
    "                        new_boxes.add(b)\n",
    "                    my_keys.discard(box)\n",
    "                    _my_boxes.remove(box)\n",
    "                next_my_boxes = _my_boxes | new_boxes\n",
    "            if next_my_boxes == my_boxes:\n",
    "                break\n",
    "            else:\n",
    "                my_boxes = next_my_boxes\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        n = len(status)\n",
    "        can_open = [status[i] == 1 for i in range(n)]\n",
    "        has_box, used = [False] * n, [False] * n\n",
    "        \n",
    "        q = collections.deque()\n",
    "        ans = 0\n",
    "        for box in initialBoxes:\n",
    "            has_box[box] = True\n",
    "            if can_open[box]:\n",
    "                q.append(box)\n",
    "                used[box] = True\n",
    "                ans += candies[box]\n",
    "        \n",
    "        while len(q) > 0:\n",
    "            big_box = q.popleft()\n",
    "            for key in keys[big_box]:\n",
    "                can_open[key] = True\n",
    "                if not used[key] and has_box[key]:\n",
    "                    q.append(key)\n",
    "                    used[key] = True\n",
    "                    ans += candies[key]\n",
    "            for box in containedBoxes[big_box]:\n",
    "                has_box[box] = True\n",
    "                if not used[box] and can_open[box]:\n",
    "                    q.append(box)\n",
    "                    used[box] = True\n",
    "                    ans += candies[box]\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        q = deque()\n",
    "        key = set()\n",
    "        box = set()\n",
    "        for i in initialBoxes:\n",
    "            if status[i]:\n",
    "                q.append(i)\n",
    "                key |= set(keys[i])\n",
    "            else:\n",
    "                box.add(i)\n",
    "            \n",
    "        ans = 0\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            ans += candies[cur]\n",
    "            key |= set(keys[cur])\n",
    "            box |= set(containedBoxes[cur])\n",
    "            for nxt in box.copy():\n",
    "                if status[nxt]:\n",
    "                    q.append(nxt)\n",
    "                    box.remove(nxt)\n",
    "                elif nxt in key:\n",
    "                    q.append(nxt)\n",
    "                    box.remove(nxt)\n",
    "                    key.remove(nxt)        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "\n",
    "        ans = 0\n",
    "        n = len(status)\n",
    "        stack = []\n",
    "        dct_key = set()\n",
    "        dct_box = set(initialBoxes)\n",
    "        for i in initialBoxes:\n",
    "            if status[i] == 1:\n",
    "                ans += candies[i]\n",
    "\n",
    "                status[i] = -1\n",
    "                stack.append(i)\n",
    "        while stack:\n",
    "            nex = []\n",
    "            for i in stack:\n",
    "                for j in keys[i]:\n",
    "                    dct_key.add(j)\n",
    "                    if j in dct_box and status[j] != -1:\n",
    "                        ans += candies[j]\n",
    "                        status[j] = -1\n",
    "                        nex.append(j)\n",
    "                for j in containedBoxes[i]:\n",
    "                    dct_box.add(j)\n",
    "                    if j in dct_key or status[j]==1:\n",
    "                        ans += candies[j]\n",
    "                        status[j] = -1\n",
    "                        nex.append(j)\n",
    "            stack = nex[:]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        q = deque()\n",
    "        key = set()\n",
    "        box = set()\n",
    "        for i in initialBoxes:\n",
    "            if status[i]:\n",
    "                q.append(i)\n",
    "                key |= set(keys[i])\n",
    "            else:\n",
    "                box.add(i)\n",
    "            \n",
    "        ans = 0\n",
    "        while q:\n",
    "            # print(\"--------\")\n",
    "            # print(ans)\n",
    "            # print(q)\n",
    "            cur = q.popleft()\n",
    "            ans += candies[cur]\n",
    "            key |= set(keys[cur])\n",
    "            # print(key)\n",
    "            # print(box)\n",
    "            box |= set(containedBoxes[cur])\n",
    "            for nxt in box.copy():\n",
    "                if status[nxt]:\n",
    "                    q.append(nxt)\n",
    "                    box.remove(nxt)\n",
    "                elif nxt in key:\n",
    "                    q.append(nxt)\n",
    "                    box.remove(nxt)\n",
    "                    key.remove(nxt)\n",
    "            \n",
    "\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        n = len(status)\n",
    "        can_open = [status[i] == 1 for i in range(n)]\n",
    "        has_box, used = [False] * n, [False] * n\n",
    "\n",
    "        q = deque()\n",
    "        ans = 0\n",
    "        # 把开着的盒子先放进去\n",
    "        for box in initialBoxes:\n",
    "            has_box[box] = True\n",
    "            if can_open[box]:\n",
    "                q.append(box)\n",
    "                used[box] = True\n",
    "                ans += candies[box]\n",
    "        \n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            for key in keys[cur]:\n",
    "                can_open[key] = True\n",
    "                if not used[key] and has_box[key]:\n",
    "                    q.append(key)\n",
    "                    used[key] = True\n",
    "                    ans += candies[key]\n",
    "            for box in containedBoxes[cur]:\n",
    "                has_box[box] = True\n",
    "                if not used[box] and can_open[box]:\n",
    "                    q.append(box)\n",
    "                    used[box] = True\n",
    "                    ans += candies[box]\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        total = 0\n",
    "        haskey = set()\n",
    "        closedboxes = []\n",
    "        pending = []\n",
    "        for i in initialBoxes:\n",
    "            if status[i]:\n",
    "                pending.append(i)\n",
    "            else:\n",
    "                closedboxes.append(i)\n",
    "\n",
    "        while pending:\n",
    "            i = pending.pop()\n",
    "            total += candies[i]\n",
    "            haskey.update(keys[i])\n",
    "            closedboxes.extend(containedBoxes[i])\n",
    "            tem = closedboxes[:]\n",
    "            for k in tem:\n",
    "                if status[k] or k in haskey:\n",
    "                    pending.append(k)\n",
    "                    closedboxes.remove(k)\n",
    "        return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        has_key = set()\n",
    "        status_set = set([i for i in range(len(status)) if status[i] == 1])\n",
    "        unboxs = set(initialBoxes) & status_set\n",
    "        boxs = set(initialBoxes) - status_set\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        while unboxs :\n",
    "            for box in unboxs:\n",
    "                boxs |= set(containedBoxes[box])\n",
    "                has_key |= set(keys[box])\n",
    "                ans += candies[box]\n",
    "            union = boxs & (has_key | status_set)\n",
    "            boxs -= union\n",
    "            has_key -= union\n",
    "            unboxs = union\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        ans = 0\n",
    "        haveBox = set()\n",
    "        havekey = set()\n",
    "        queue = deque()\n",
    "\n",
    "        for i in initialBoxes:\n",
    "            if status[i]:\n",
    "                queue.append(i)\n",
    "            else:\n",
    "                haveBox.add(i)\n",
    "        \n",
    "        while queue:\n",
    "            box = queue.popleft()\n",
    "            ans += candies[box]\n",
    "            for i in containedBoxes[box]:\n",
    "                if status[i]:\n",
    "                    queue.append(i)\n",
    "                else:\n",
    "                    haveBox.add(i)\n",
    "            for i in keys[box]:\n",
    "                havekey.add(i)\n",
    "            rm = set()\n",
    "            for i in haveBox:\n",
    "                if i in havekey:\n",
    "                    queue.append(i)\n",
    "                    rm.add(i)\n",
    "            haveBox = haveBox - rm\n",
    "            havekey = havekey - rm\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        res = 0\n",
    "        can_open = [i for i in initialBoxes if status[i]==1]\n",
    "        cannot_open = [i for i in initialBoxes if status[i]==0]\n",
    "        while can_open:\n",
    "            for x in can_open:\n",
    "                res += candies[x]\n",
    "                cannot_open += containedBoxes[x]\n",
    "                for key in keys[x]: status[key] = 1\n",
    "            can_open = [i for i in cannot_open if status[i]==1]\n",
    "            cannot_open = [i for i in cannot_open if status[i]==0]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        n = len(status)\n",
    "        # 直接可以打开的盒子不需要钥匙\n",
    "        can_open = [status[i] == 1 for i in range(n)]\n",
    "        has_box, used = [False] * n, [False] * n\n",
    "\n",
    "        q = deque()\n",
    "        ans = 0\n",
    "        for box in initialBoxes:\n",
    "            has_box[box] = True\n",
    "            if can_open[box]:\n",
    "                q.append(box)\n",
    "                used[box] = True\n",
    "                ans += candies[box]\n",
    "        \n",
    "        while q:\n",
    "            big_box = q.popleft()\n",
    "            # 统计钥匙\n",
    "            for key in keys[big_box]:\n",
    "                can_open[key] = True\n",
    "                if not used[key] and has_box[key]:\n",
    "                    q.append(key)\n",
    "                    used[key] = True\n",
    "                    ans += candies[key]\n",
    "            # 统计盒子\n",
    "            for box in containedBoxes[big_box]:\n",
    "                has_box[box] = True\n",
    "                if not used[box] and can_open[box]:\n",
    "                    q.append(box)\n",
    "                    used[box] = True\n",
    "                    ans += candies[box]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# 遇到盒子：\n",
    "#     1、将盒子放到盒子集合boxes\n",
    "#     2、将盒子集合中没有上锁的盒子入队列q。\n",
    "# 遇到钥匙：\n",
    "#     1、如果对应的盒子之前就已经在盒子集合中且之前没有解锁，则加入队列q\n",
    "#     2、将对应的盒子解锁（修改 status 数组）\n",
    "class Solution:\n",
    "    def maxCandies(self, status, candies, keys, containedBoxes, initialBoxes):\n",
    "        boxes = set(initialBoxes)\n",
    "        q = [i for i in boxes if status[i]]\n",
    "        for i in q:\n",
    "            for j in containedBoxes[i]:\n",
    "                boxes.add(j)\n",
    "                if status[j]:\n",
    "                    q.append(j)\n",
    "            for j in keys[i]:\n",
    "                if status[j] == 0 and j in boxes:\n",
    "                    q.append(j)\n",
    "                status[j] = 1\n",
    "\n",
    "        return sum(candies[i] for i in q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        ans = 0\n",
    "        q = deque()\n",
    "        boxs = []\n",
    "        vis = [0] * len(status)\n",
    "        for x in initialBoxes:\n",
    "            boxs.append(x)\n",
    "            if status[x]:\n",
    "                q.append(x)\n",
    "                ans += candies[x]\n",
    "                vis[x] = 1\n",
    "        while q:\n",
    "            p = q.popleft()\n",
    "            for x in keys[p]:\n",
    "                status[x] = 1\n",
    "            for nx in containedBoxes[p]:\n",
    "                boxs.append(nx)\n",
    "            for nx in boxs:\n",
    "                if not status[nx] or vis[nx]:\n",
    "                    continue\n",
    "                ans += candies[nx]\n",
    "                q.append(nx)\n",
    "                vis[nx] = 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "      current_keys = set()\n",
    "      current_boxes = set(initialBoxes)\n",
    "\n",
    "      candy = 0\n",
    "\n",
    "      def open_box(i):\n",
    "        if i not in current_boxes or (i not in current_keys and status[i] != 1):\n",
    "          return\n",
    "\n",
    "        current_boxes.remove(i)\n",
    "        if status[i] == 0:\n",
    "          current_keys.remove(i)\n",
    "\n",
    "        nonlocal candy\n",
    "        candy += candies[i]\n",
    "\n",
    "        for key in keys[i]:\n",
    "          current_keys.add(key)\n",
    "\n",
    "        for box in containedBoxes[i]:\n",
    "          current_boxes.add(box)\n",
    "\n",
    "      while True:\n",
    "        last = candy\n",
    "\n",
    "        for box in current_boxes.copy():\n",
    "          open_box(box)\n",
    "\n",
    "        if candy == last:\n",
    "          return candy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:    \n",
    "        # 可打开的状态\n",
    "        valid = set()\n",
    "        for idx, open in enumerate(status):\n",
    "            if open == 1:\n",
    "                valid.add(idx)\n",
    "        # 是否入队\n",
    "        vis = set()\n",
    "        # 拥有的盒子\n",
    "        holdbox = set()\n",
    "        ans = 0\n",
    "        q = deque()\n",
    "\n",
    "        for idx in initialBoxes:\n",
    "            holdbox.add(idx)\n",
    "            if idx in valid:\n",
    "                q.append(idx)\n",
    "                vis.add(idx)\n",
    "                ans += candies[idx]\n",
    "        \n",
    "        while q:\n",
    "            idx = q.popleft()\n",
    "            # 先看里面的钥匙\n",
    "            for key in keys[idx]:\n",
    "                # 有箱子，且箱子没用过\n",
    "                valid.add(key)\n",
    "                if key in holdbox and not key in vis:\n",
    "                    q.append(key)\n",
    "                    vis.add(key)\n",
    "                    ans += candies[key]\n",
    "            # 再枚举里面的箱子\n",
    "            for box in containedBoxes[idx]:\n",
    "                holdbox.add(box)\n",
    "                if not box in vis and box in valid:\n",
    "                    q.append(box)\n",
    "                    vis.add(box)\n",
    "                    ans += candies[box]\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        boxkeys = set()\n",
    "\n",
    "        for i, state in enumerate(status):\n",
    "            if state == 1:\n",
    "                boxkeys.add(i)\n",
    "\n",
    "        visited = set()\n",
    "        boxes = set(initialBoxes)\n",
    "\n",
    "        queue = deque()\n",
    "\n",
    "        for box in initialBoxes:\n",
    "            boxes.add(box)\n",
    "            if box in boxkeys and box not in visited:\n",
    "                visited.add(box)\n",
    "                queue.append(box)\n",
    "\n",
    "        candy = 0\n",
    "        while queue:\n",
    "            outter = queue.popleft()\n",
    "            candy += candies[outter]\n",
    "\n",
    "            for key in keys[outter]:\n",
    "                boxkeys.add(key)\n",
    "                if key in boxes and key not in visited:\n",
    "                    visited.add(key)\n",
    "                    queue.append(key)\n",
    "\n",
    "            for box in containedBoxes[outter]:\n",
    "                boxes.add(box)\n",
    "                if box in boxkeys and box not in visited:\n",
    "                    visited.add(box)\n",
    "                    queue.append(box)\n",
    "\n",
    "        return candy\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:    \n",
    "        # 可打开的状态\n",
    "        valid = set()\n",
    "        for idx, open in enumerate(status):\n",
    "            if open == 1:\n",
    "                valid.add(idx)\n",
    "        # 是否入队\n",
    "        vis = set()\n",
    "        # 拥有的盒子\n",
    "        holdbox = set()\n",
    "        ans = 0\n",
    "        q = deque()\n",
    "\n",
    "        for idx in initialBoxes:\n",
    "            holdbox.add(idx)\n",
    "            if idx in valid:\n",
    "                q.append(idx)\n",
    "                vis.add(idx)\n",
    "                ans += candies[idx]\n",
    "        \n",
    "        while q:\n",
    "            idx = q.popleft()\n",
    "            # 先看里面的钥匙\n",
    "            for key in keys[idx]:\n",
    "                # 有箱子，且箱子没用过\n",
    "                valid.add(key)\n",
    "                if key in holdbox and not key in vis:\n",
    "                    q.append(key)\n",
    "                    vis.add(key)\n",
    "                    ans += candies[key]\n",
    "            # 再枚举里面的箱子\n",
    "            for box in containedBoxes[idx]:\n",
    "                holdbox.add(box)\n",
    "                if not box in vis and box in valid:\n",
    "                    q.append(box)\n",
    "                    vis.add(box)\n",
    "                    ans += candies[box]\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status, candies, keys, containedBoxes, initialBoxes):\n",
    "        ans = 0\n",
    "        res = set() # 存钥匙\n",
    "\n",
    "        flag=True\n",
    "        while flag:\n",
    "            flag = False\n",
    "            n = len(initialBoxes)\n",
    "            for i in range(n):\n",
    "                t = initialBoxes[i]\n",
    "                if t == -1:\n",
    "                    continue\n",
    "                if status[t] == 0 and t not in res:\n",
    "                    continue\n",
    "                flag = True\n",
    "                ans += candies[t]\n",
    "                res.update(keys[t])\n",
    "                initialBoxes += containedBoxes[t]\n",
    "                initialBoxes[i] = -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        q = deque()\n",
    "        q_k = set()\n",
    "        k = set()\n",
    "        for b in initialBoxes:\n",
    "            if status[b] == 1:\n",
    "                q.append(b)\n",
    "            else:\n",
    "                q_k.add(b)\n",
    "        res = 0\n",
    "        while q:\n",
    "            bx = q.popleft()\n",
    "            res += candies[bx]\n",
    "            for b in containedBoxes[bx]:\n",
    "                if status[b] == 1:\n",
    "                    q.append(b)\n",
    "                elif b in k:\n",
    "                    q.append(b)\n",
    "                    k.remove(b)\n",
    "                else:\n",
    "                    q_k.add(b)\n",
    "            for ks in keys[bx]:\n",
    "                if ks in q_k:\n",
    "                    q.append(ks)\n",
    "                    q_k.remove(ks)\n",
    "                else:\n",
    "                    k.add(ks)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        n = len(status)\n",
    "        ans = 0\n",
    "        has_box = [False] * n\n",
    "        used = [False] * n \n",
    "        queue = deque()\n",
    "\n",
    "        for box in initialBoxes:\n",
    "            has_box[box] = True \n",
    "            if status[box]:\n",
    "                queue.append(box)\n",
    "                used[box] = True \n",
    "                ans += candies[box]\n",
    "        \n",
    "        while queue:\n",
    "            box = queue.popleft()\n",
    "\n",
    "            for key in keys[box]:\n",
    "                status[key] = 1\n",
    "                if not used[key] and has_box[key]:\n",
    "                    queue.append(key)\n",
    "                    used[key] = True \n",
    "                    ans += candies[key]\n",
    "            \n",
    "            for sub_box in containedBoxes[box]:\n",
    "                has_box[sub_box] = True \n",
    "                if not used[sub_box] and status[sub_box]:\n",
    "                    queue.append(sub_box)\n",
    "                    used[sub_box] = True \n",
    "                    ans += candies[sub_box]\n",
    "        \n",
    "        return ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        q = deque()\n",
    "        q_k = set()\n",
    "        k = set()\n",
    "        for b in initialBoxes:\n",
    "            if status[b] == 1:\n",
    "                q.append(b)\n",
    "            else:\n",
    "                q_k.add(b)\n",
    "        res = 0\n",
    "        while q:\n",
    "            bx = q.popleft()\n",
    "            res += candies[bx]\n",
    "            for b in containedBoxes[bx]:\n",
    "                if status[b] == 1:\n",
    "                    q.append(b)\n",
    "                elif b in k:\n",
    "                    q.append(b)\n",
    "                    k.remove(b)\n",
    "                else:\n",
    "                    q_k.add(b)\n",
    "            for ks in keys[bx]:\n",
    "                if ks in q_k:\n",
    "                    q.append(ks)\n",
    "                    q_k.remove(ks)\n",
    "                else:\n",
    "                    k.add(ks)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        ans = 0\n",
    "        res = set() # 存钥匙\n",
    "\n",
    "        flag=True\n",
    "        while flag:\n",
    "            flag = False\n",
    "            n = len(initialBoxes)\n",
    "            for i in range(n):\n",
    "                t = initialBoxes[i]\n",
    "                if t == -1:\n",
    "                    continue\n",
    "                if status[t] == 0 and t not in res:\n",
    "                    continue\n",
    "                flag = True\n",
    "                ans += candies[t]\n",
    "                res.update(keys[t])\n",
    "                initialBoxes += containedBoxes[t]\n",
    "                initialBoxes[i] = -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\r\n",
    "        locked: set[int] = set()\r\n",
    "        q: deque[int] = deque()\r\n",
    "        for box in initialBoxes:\r\n",
    "            if status[box] == 1:\r\n",
    "                q.append(box)\r\n",
    "            else:\r\n",
    "                locked.add(box)\r\n",
    "        \r\n",
    "        res = 0\r\n",
    "        while q:\r\n",
    "            box = q.popleft()\r\n",
    "            res += candies[box]\r\n",
    "            for key in keys[box]:\r\n",
    "                status[key] = 1\r\n",
    "                if key in locked:\r\n",
    "                    locked.remove(key)\r\n",
    "                    q.append(key)\r\n",
    "            for nxt_box in containedBoxes[box]:\r\n",
    "                if status[nxt_box] == 1:\r\n",
    "                    q.append(nxt_box)\r\n",
    "                else:\r\n",
    "                    locked.add(nxt_box)\r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        n=len(status)\n",
    "        vis=[0]*n\n",
    "        havkey=[0]*n\n",
    "        stack=initialBoxes\n",
    "        cnt=0\n",
    "        while stack:\n",
    "            f=0\n",
    "            nexstack=[]\n",
    "            for i in range(len(stack)):\n",
    "                i=stack[i]\n",
    "                if vis[i]==1:\n",
    "                    continue\n",
    "                if status[i]==1:\n",
    "                    vis[i]=1\n",
    "                    f=1\n",
    "                    cnt+=candies[i]\n",
    "                    for k in keys[i]:\n",
    "                        havkey[k]=1\n",
    "                    for c in containedBoxes[i]:\n",
    "                        if vis[c]==0:\n",
    "                            nexstack.append(c)\n",
    "                elif status[i]==0:\n",
    "                    if havkey[i]==1:\n",
    "                        vis[i]=1\n",
    "                        f=1\n",
    "                        cnt+=candies[i]\n",
    "                        for k in keys[i]:\n",
    "                            havkey[k]=1\n",
    "                        for c in containedBoxes[i]:\n",
    "                            if vis[c]==0:\n",
    "                                nexstack.append(c)\n",
    "                    else:\n",
    "                        nexstack.append(i)\n",
    "            if f==0:\n",
    "                break\n",
    "            stack=nexstack\n",
    "        return cnt\n",
    "\n",
    "                \n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        Q = deque()\n",
    "        n = len(status)\n",
    "        vis = [0] * n \n",
    "        for x in initialBoxes:\n",
    "            vis[x] |= 1 \n",
    "            if status[x] == 1:\n",
    "                vis[x] = 3 \n",
    "                Q.append(x)\n",
    "        tot = 0 \n",
    "        while Q:\n",
    "            u = Q.popleft()\n",
    "            tot += candies[u] \n",
    "            for v in containedBoxes[u]:\n",
    "                if vis[v] == 3:\n",
    "                    continue \n",
    "                if status[v] == 1:\n",
    "                    vis[v] = 3 \n",
    "                    Q.append(v) \n",
    "                else:\n",
    "                    vis[v] |= 1 \n",
    "                    if vis[v] == 3:\n",
    "                        Q.append(v) \n",
    "            for k in keys[u]:\n",
    "                if vis[k] == 3:\n",
    "                    continue \n",
    "                vis[k] |= 2 \n",
    "                if vis[k] == 3:\n",
    "                    Q.append(k) \n",
    "        return tot \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\r\n",
    "        res = 0\r\n",
    "        n = len(status)\r\n",
    "        q = [x for x in initialBoxes if status[x]] # 存放已经打开但没访问的盒子\r\n",
    "        vis = [False] * n                          # 盒子是否被访问过\r\n",
    "        for x in q:\r\n",
    "            vis[x] = True\r\n",
    "        havebox = [False] * n                      # 是否拥有某一个盒子\r\n",
    "        for x in initialBoxes:\r\n",
    "            havebox[x] = True \r\n",
    "        while q:\r\n",
    "            tmp = q \r\n",
    "            q = []\r\n",
    "            for x in tmp:\r\n",
    "                res += candies[x] \r\n",
    "                for key in keys[x]:\r\n",
    "                    status[key] = 1 \r\n",
    "                    if havebox[key] and not vis[key]:\r\n",
    "                        vis[key] = True\r\n",
    "                        q.append(key)\r\n",
    "                for box in containedBoxes[x]:\r\n",
    "                    havebox[box] = True \r\n",
    "                    if status[box] and not vis[box]:\r\n",
    "                        vis[box] = True\r\n",
    "                        q.append(box)\r\n",
    "        return res \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        q = deque()\n",
    "        q_k = set()\n",
    "        k = set()\n",
    "        for b in initialBoxes:\n",
    "            if status[b] == 1:\n",
    "                q.append(b)\n",
    "            else:\n",
    "                q_k.add(b)\n",
    "        res = 0\n",
    "        while q:\n",
    "            bx = q.popleft()\n",
    "            res += candies[bx]\n",
    "            for b in containedBoxes[bx]:\n",
    "                if status[b] == 1 or b in k:\n",
    "                    q.append(b)\n",
    "                else:\n",
    "                    q_k.add(b)\n",
    "            for ks in keys[bx]:\n",
    "                if ks in q_k:\n",
    "                    q.append(ks)\n",
    "                    q_k.remove(ks)\n",
    "                else:\n",
    "                    k.add(ks)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        box_queue=[]\n",
    "        n=len(status)\n",
    "        haskey=[False]*n\n",
    "        vis=[False]*n \n",
    "        for x in initialBoxes:\n",
    "            vis[x]=True\n",
    "            if status[x]==1:\n",
    "                box_queue.append(x)\n",
    "                status[x]=2\n",
    "        ans=0\n",
    "        while box_queue:\n",
    "            b=box_queue.pop(0)\n",
    "            ans+=candies[b]\n",
    "            for c in containedBoxes[b]:\n",
    "                if status[c]==1:\n",
    "                    box_queue.append(c)\n",
    "                    status[c]=2\n",
    "                elif status[c]==0:\n",
    "                    vis[c]=True\n",
    "                    if haskey[c]:\n",
    "                        box_queue.append(c)\n",
    "                        status[c]=2\n",
    "            for k in keys[b]:\n",
    "                haskey[k]=True\n",
    "                if status[k]==0 and vis[k]:\n",
    "                    box_queue.append(k)\n",
    "                    status[k]=2\n",
    "        return ans\n",
    "                    \n",
    "                \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        res = 0\n",
    "        q = deque(initialBoxes)\n",
    "        gain = set(initialBoxes)\n",
    "        ok = set()\n",
    "        while q:\n",
    "            now = q.popleft()\n",
    "            if status[now] and now not in ok:\n",
    "                res += candies[now]\n",
    "                ok.add(now)\n",
    "                for key in keys[now]:\n",
    "                    status[key] = 1\n",
    "                    if key in gain:\n",
    "                        q.append(key)\n",
    "                for nex in containedBoxes[now]:\n",
    "                    q.append(nex)\n",
    "                    gain.add(nex)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        que = deque()\n",
    "        initialBoxes = set(initialBoxes)\n",
    "        for box in initialBoxes:\n",
    "            if status[box]:\n",
    "                que.append(box)\n",
    "        ans = 0\n",
    "        vis = set(que)\n",
    "        while que:\n",
    "            x = que.popleft()\n",
    "            ans += candies[x]\n",
    "            for key in keys[x]:\n",
    "                if key in initialBoxes and key not in vis:\n",
    "                    vis.add(key)\n",
    "                    que.append(key)\n",
    "                status[key] = 1\n",
    "            for box in containedBoxes[x]:\n",
    "                if status[box] and box not in vis:\n",
    "                    vis.add(box)\n",
    "                    que.append(box)\n",
    "                else:\n",
    "                    initialBoxes.add(box)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        opening = []\n",
    "        n = len(status)\n",
    "        haveKey = set()\n",
    "        haveBox = set()\n",
    "        opened = set()\n",
    "        for i in range(n):\n",
    "            if status[i] == 1:\n",
    "                haveKey.add(i)\n",
    "        for box in initialBoxes:\n",
    "            if box in haveKey:\n",
    "                opening.append(box)\n",
    "                opened.add(box)\n",
    "            else:\n",
    "                haveBox.add(box)\n",
    "        res = 0\n",
    "        s = 0\n",
    "        while s < len(opening):\n",
    "            box = opening[s]\n",
    "            res += candies[box]\n",
    "            for key in keys[box]:\n",
    "                if key in haveBox and key not in opened:\n",
    "                    opening.append(key)\n",
    "                    opened.add(key)\n",
    "                else:\n",
    "                    haveKey.add(key)\n",
    "            for box2 in containedBoxes[box]:\n",
    "                if box2 in haveKey and box2 not in opened:\n",
    "                    opening.append(box2)\n",
    "                    opened.add(box2)\n",
    "                else:\n",
    "                    haveBox.add(box2)\n",
    "\n",
    "            s += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        ans = 0\n",
    "        open_ = True\n",
    "        while initialBoxes and open_:\n",
    "            open_ = False\n",
    "            nex = []\n",
    "            for i in initialBoxes:\n",
    "                if status[i] == 1:\n",
    "                    open_ = True\n",
    "                    ans += candies[i]\n",
    "                    candies[i] = 0\n",
    "                    for j in keys[i]:\n",
    "                        status[j] = 1\n",
    "                    nex.extend(containedBoxes[i])\n",
    "                else:\n",
    "                    nex.append(i)\n",
    "            initialBoxes = nex[:]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "\n",
    "        res = 0\n",
    "        kset = [0]*len(status)\n",
    "        nokey = [0]*len(status)\n",
    "        visited = [0]*len(status)\n",
    "        \n",
    "        # BFS直接搜索\n",
    "        q = deque()\n",
    "        for i in range(len(initialBoxes)):\n",
    "            if status[initialBoxes[i]] == 1:\n",
    "                q.append(initialBoxes[i])\n",
    "            else:\n",
    "                nokey[initialBoxes[i]] = 1\n",
    "        \n",
    "        \n",
    "        while q:\n",
    "            # print(q)\n",
    "            for _ in range(len(q)):\n",
    "                cur = q.popleft()\n",
    "                res += candies[cur]\n",
    "                visited[cur] = 1\n",
    "                for i in keys[cur]:\n",
    "                    kset[i] = 1\n",
    "                for i in containedBoxes[cur]:\n",
    "                    nokey[i] = 1\n",
    "            \n",
    "            for i in range(len(kset)):\n",
    "                if status[i] == nokey[i] == 1 and visited[i] != 1:\n",
    "                    q.append(i)\n",
    "                    continue   \n",
    "                if kset[i] == nokey[i] == 1 and visited[i] != 1:\n",
    "                    q.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status, candies, keys, containedBoxes, initialBoxes):\n",
    "        res=0\n",
    "        curkey=[]\n",
    "        curBoxes=initialBoxes[:]\n",
    "        while True:\n",
    "            temp=curBoxes[:]\n",
    "            for box in temp:\n",
    "                if status[box]==1 or (status[box]==0 and box in curkey):\n",
    "                    res += candies[box]  # 将糖果拿出来\n",
    "                    curkey += keys[box]  # 将钥匙拿出来\n",
    "                    curBoxes.remove(box)\n",
    "\n",
    "                    curBoxes += containedBoxes[box]  # 从中取出内含的盒子\n",
    "                    break\n",
    "            else:\n",
    "                return res\n",
    "\n",
    "\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        hand_box = initialBoxes\n",
    "        hand_key = []\n",
    "        count = 0\n",
    "        while hand_box:\n",
    "            tmp = []\n",
    "            c = 0\n",
    "            for i in range(len(hand_box)):\n",
    "                curr_box = hand_box[i]\n",
    "                if status[curr_box] == 1 or curr_box in hand_key:\n",
    "                    count += candies[curr_box]\n",
    "                    curr_inBox_keys = keys[curr_box]\n",
    "                    hand_key += curr_inBox_keys\n",
    "                    curr_inBox_Box = containedBoxes[curr_box]\n",
    "                    tmp += curr_inBox_Box\n",
    "                    continue\n",
    "                c += 1\n",
    "                tmp.append(curr_box)\n",
    "            if c == len(hand_box):\n",
    "                break\n",
    "            hand_box = tmp\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        hand_box = initialBoxes\n",
    "        hand_key = []\n",
    "        count = 0\n",
    "        while hand_box:\n",
    "            tmp = []\n",
    "            c = 0\n",
    "            for i in range(len(hand_box)):\n",
    "                curr_box = hand_box[i]\n",
    "                if status[curr_box] == 1 or curr_box in hand_key:\n",
    "                    count += candies[curr_box]\n",
    "                    curr_inBox_keys = keys[curr_box]\n",
    "                    hand_key += curr_inBox_keys\n",
    "                    curr_inBox_Box = containedBoxes[curr_box]\n",
    "                    tmp += curr_inBox_Box\n",
    "                    continue\n",
    "                c += 1\n",
    "                tmp.append(curr_box)\n",
    "            if c == len(hand_box):\n",
    "                break\n",
    "            hand_box = tmp\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, states, candys, keys, conboxs, iniboxs):\n",
    "        # 当前已有的盒子，维护成一个队列。\n",
    "        line = deque(iniboxs)\n",
    "        # 当前已有的钥匙。\n",
    "        have = []\n",
    "        # 糖果数量。\n",
    "        result = 0\n",
    "        flag = True\n",
    "        old_box, old_now = [], -1\n",
    "        # 队列非空。\n",
    "        while line:\n",
    "            # 当前的盒子。\n",
    "            now = line.popleft()\n",
    "            # 可以打开：在拥有盒子的情况下，盒子本身打开或者拥有盒子的钥匙。\n",
    "            if states[now] or now in have:\n",
    "                result += candys[now]\n",
    "                # 新增盒子。\n",
    "                line.extend(conboxs[now])\n",
    "                # 新增钥匙。\n",
    "                have.extend(keys[now])\n",
    "                if now == old_now:\n",
    "                    flag = True\n",
    "            # 不可以打开。\n",
    "            else:\n",
    "                line.append(now)\n",
    "                if flag:\n",
    "                    old_box = line.copy()\n",
    "                    old_now = now\n",
    "                    flag = False\n",
    "                # 判断队列是否改变。\n",
    "                elif not flag and now == old_now:\n",
    "                    if old_box == line:\n",
    "                        break\n",
    "                    old_box = line.copy()\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        hand_box = initialBoxes\n",
    "        hand_key = []\n",
    "        count = 0\n",
    "        while hand_box:\n",
    "            tmp = []\n",
    "            c = 0\n",
    "            for i in range(len(hand_box)):\n",
    "                curr_box = hand_box[i]\n",
    "                if status[curr_box] == 1 or curr_box in hand_key:\n",
    "                    count += candies[curr_box]\n",
    "                    curr_inBox_keys = keys[curr_box]\n",
    "                    hand_key += curr_inBox_keys\n",
    "                    curr_inBox_Box = containedBoxes[curr_box]\n",
    "                    tmp += curr_inBox_Box\n",
    "                    continue\n",
    "                c += 1\n",
    "                tmp.append(curr_box)\n",
    "            if c == len(hand_box):\n",
    "                break\n",
    "            hand_box = tmp\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        num = 0\n",
    "        store_key = []\n",
    "\n",
    "        while True:\n",
    "            flg = False\n",
    "            #盒子中全都没钥匙且打不开，则退出循环\n",
    "            for v in initialBoxes:\n",
    "                if v == -1:\n",
    "                    continue\n",
    "                if status[v] == 1 or v in store_key:\n",
    "                    flg = True\n",
    "                    break\n",
    "\n",
    "            if not flg:\n",
    "                break\n",
    "\n",
    "            for i in range(len(initialBoxes)):\n",
    "                v = initialBoxes[i]\n",
    "                if v == -1:\n",
    "                    continue\n",
    "                #没打开且没有钥匙\n",
    "                if status[v] == 0 and v not in store_key:\n",
    "                    continue\n",
    "                num += candies[v]\n",
    "                store_key += keys[v]\n",
    "                initialBoxes += containedBoxes[v]\n",
    "                initialBoxes[i] = -1\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        boxes = initialBoxes\n",
    "        exist_keys = []\n",
    "        i = 0\n",
    "        result = 0\n",
    "        # i为当前不可打开的箱子数量\n",
    "        while i < len(boxes):\n",
    "            for ibox in boxes:\n",
    "                # 判断箱子列表内的箱子是否能打开，能打开的处理数据后移除列表;\n",
    "                if status[ibox] or ibox in exist_keys:\n",
    "                    result += candies[ibox]\n",
    "                    boxes.extend(containedBoxes[ibox])\n",
    "                    exist_keys.extend(keys[ibox])\n",
    "                    boxes.remove(ibox)\n",
    "                    i = 0\n",
    "                    # 每次打开一个箱子后，重新进入循环:因打开箱子可能获取到新箱子/新钥匙\n",
    "                    break\n",
    "                i += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        count = 0\n",
    "        keys1 = []\n",
    "        boxes1 = initialBoxes[:]\n",
    "        while True:\n",
    "            for i in boxes1:\n",
    "                if status[i] == 1 or i in keys1:\n",
    "                    count += candies[i]\n",
    "                    keys1 += keys[i]\n",
    "                    boxes1.remove(i)\n",
    "                    boxes1 += containedBoxes[i]\n",
    "                    break\n",
    "            else:\n",
    "                return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "    count = 0\n",
    "    keys1 = []\n",
    "    boxes1 = initialBoxes[:]\n",
    "    while True:\n",
    "      for i in boxes1:\n",
    "        if status[i] == 1 or i in keys1:\n",
    "          count += candies[i]\n",
    "          keys1 += keys[i]\n",
    "          boxes1.remove(i)\n",
    "          boxes1 += containedBoxes[i]\n",
    "          break\n",
    "      else:\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        count = 0\n",
    "        keys1 = []\n",
    "        boxes1 = initialBoxes[:]\n",
    "        while True:\n",
    "            for i in boxes1:\n",
    "                if status[i] == 1 or i in keys1:\n",
    "                    count += candies[i]\n",
    "                    keys1 += keys[i]\n",
    "                    boxes1.remove(i)\n",
    "                    boxes1 += containedBoxes[i]\n",
    "                    break\n",
    "            else:\n",
    "                return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        count = 0\n",
    "        keys1 = []\n",
    "        boxes1 = initialBoxes[:]\n",
    "        while True:\n",
    "            for i in boxes1:\n",
    "                if status[i] == 1 or i in keys1:\n",
    "                    count += candies[i]\n",
    "                    keys1 += keys[i]\n",
    "                    boxes1.remove(i)\n",
    "                    boxes1 += containedBoxes[i]\n",
    "                    break\n",
    "            else:\n",
    "                return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "     def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        count = 0\n",
    "        keys1 = []\n",
    "        boxes1 = initialBoxes[:]\n",
    "        while True:\n",
    "            for i in boxes1:\n",
    "                if status[i] == 1 or i in keys1:\n",
    "                    count += candies[i]\n",
    "                    keys1 += keys[i]\n",
    "                    boxes1.remove(i)\n",
    "                    boxes1 += containedBoxes[i]\n",
    "                    break\n",
    "            else:\n",
    "                return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "        current_keys=[]\n",
    "\n",
    "        current_box=initialBoxes\n",
    "\n",
    "        c_num=0\n",
    "\n",
    "        while len(current_box)!=0:\n",
    "            flag=False\n",
    "            target_box=-1\n",
    "            for i in range(len(current_box)):\n",
    "                now_box=current_box[i]\n",
    "                state=status[now_box]\n",
    "                if(state==1):\n",
    "                    target_box=now_box\n",
    "                    break\n",
    "                else:\n",
    "                    if now_box not in current_keys:\n",
    "                        continue\n",
    "                    else:\n",
    "                        target_box=now_box\n",
    "                        break\n",
    "\n",
    "            if(target_box==-1):\n",
    "                break\n",
    "\n",
    "            c_num+=candies[target_box]\n",
    "            current_keys.extend(keys[target_box])\n",
    "            current_box.extend(containedBoxes[target_box])\n",
    "\n",
    "            current_box.remove(target_box)\n",
    "\n",
    "\n",
    "        return c_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:\n",
    "            count = 0\n",
    "            keys1 = []\n",
    "            boxes1 = initialBoxes[:]\n",
    "            while True:\n",
    "                  for i in boxes1:\n",
    "                        if status[i] == 1 or i in keys1:\n",
    "                              count += candies[i]\n",
    "                              keys1 += keys[i]\n",
    "                              boxes1.remove(i)\n",
    "                              boxes1 += containedBoxes[i]\n",
    "                              break\n",
    "                  else:\n",
    "                        return count"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
